import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/8 21:07
 * @description 进阶，输出总和最低的路径，（如果有多个答案，返回其中一个即可）
 */
public class Solution3 {
    int m, n;

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        Solution3 solution = new Solution3();
        solution.minPathSum(grid);
    }

    public int minPathSum(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        // f[i][j]表示到达位置 i,j的最短长度
        int[][] f = new int[m][n];
        // g用来存储路径，因为原问题为从 (0,0) -> (m-1,n-1)，需要扫描完整个方块才能得到最终答案，那么需要回推
        int[] g = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[i][j] = grid[i][j];
                } else {
                    int top  = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
                    int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
                    f[i][j] = Math.min(top, left);
                    g[getIdx(i, j)] = top < left ? getIdx(i - 1, j) : getIdx(i, j - 1);
                }
            }
        }

        // 从「结尾」开始，在 g[] 数组中找「上一步」
        int idx = getIdx(m - 1, n - 1);
        // 逆序将路径点添加到 path 数组中
        int[][] path = new int[m + n][2];
        path[m + n - 1] = new int[]{m - 1, n - 1};
        for (int i = 1; i < m + n; i++) {
            path[m + n - 1 - i] = parseIdx(g[idx]);
            idx = g[idx];
        }
        // 顺序输出位置
        for (int i = 1; i < m + n; i++) {
            int x = path[i][0], y = path[i][1];
            System.out.print("(" + x + "," + y + ") ");
        }
        System.out.println(" ");

        return f[m - 1][n - 1];
    }
    int[] parseIdx(int idx) {
        return new int[]{idx / n, idx % n};
    }
    int getIdx(int x, int y) {
        return x * n + y;
    }




}
